The Transmission Control Protocol/Internet Protocol suite is a widely-used transport protocol in digital packet networks. The Internet Protocol is described by Postel in Request For Comments (RFC) 791 of the U.S. Defense Advanced Research Projects Agency (DARPA), published in 1981, which is incorporated herein by reference. The Internet Protocol (IP) enables an IP datagram to be split into two or more IP fragments when an interface is unable to transmit the original datagram due to the latter being too large. The oversized datagram is split into separate IP fragments, each fragment being small enough to be transmitted by the interface. The process of fragmentation may occur more than once, depending on the maximum transmission unit (MTU) of each network component. For example, a datagram which is originally 1518 bytes—the maximum datagram size for networks operating according to an Ethernet protocol—may be sent to a first router having an MTU of 1000. The router divides the datagram into two IP fragments, 1000 bytes and 518 bytes, and forwards the two fragments to a second router having an MTU of 576 bytes, The second router divides the 1000 byte fragment into a 576 byte fragment and a 423 byte fragment, and thus transmits three fragments representing the original 1518 byte datagram.
The IP layer at the receiving host accumulates the fragments until enough have arrived to reconstitute the original datagram. RFC 791 describes a reassembly mechanism, and an algorithm for reassembly based on tracking arriving fragments in a vector of bits. The algorithm operates in substantially the same manner regardless of the number of fragments.
FIG. 1 is a diagram of IP header 10, as described in RFC 791. Header 10 is prefixed to a message from a transport protocol, so forming a datagram or a fragment of a datagram. Header 10 is formed of 20 or more bytes. Fields 12, 14, and 16 respectively represent a version number, a length of header 10, and a type of service supported. A field 18 gives a total length of the datagram or fragment, in bytes, including header 10 and data. An identification field 20 is assigned by the sender as an aid to assembling datagrams.
A field 22 comprises 1-bit flags 24, 26, and 28, and a 13-bit fragment offset 30. Flag 24 must be set to zero. Flag 26 is set to 0 if the datagram may be fragmented, and is set to 1 if the datagram may not be fragmented. Flag 28 is set to 0 to indicate that this fragment is the last fragment, and is set to 1 to indicate that there are more fragments. Fragment offset 30 indicates where in the datagram the fragment belongs. It is calculated in units of 8 bytes, and is set to 0 for the first fragment. Field 22 is used by the datagram receiver to know in which order fragments are placed, and in order to correctly reassemble the fragments to the original datagram.
RFC 815, “IP Datagram Reassembly Algorithms,” by David D. Clark, published in 1982, which is incorporated herein by reference, describes an alternative fragment reassembly system to that described in RFC 791. RFC 815 refers to a partially reassembled datagram which is assumed to have missing areas, termed holes. Each hole is characterized by the first byte number and a last byte number of the hole, the pair of numbers being termed a hole descriptor. A processor stores each hole descriptor, together with a pointer to the next hole, in its respective hole. The partially reassembled datagram is stored with its hole decriptors, by the processor, in a reassembly buffer. (The buffer size must be sufficient to accommodate the largest datagram transmitted by IP.) The buffer also maintains a global pointer to the first hole in the datagram.
As long as network speed was the main factor limiting receiver rates, software implementations of IP receiver logic provided adequate performance levels. However, with the advent of network speeds in the 1 Gbps and 10 Gbps range, this is no longer the case. Faster IP receiver processing is required, requiring a new approach to the original specifications in RFC 791 and/or RFC 815. Among the issues to be addressed are maximization of parallel processing, efficient information passing, and rapid classification and handling of fragments.